package lc20240623;

import java.util.*;

/**
  * @description 查找和最小的 K 对数字
  * @author 不知名帅哥
  * @date 2024/6/23 15:09
  * @version 1.0
*/
public class FindSmallestKArrays {
    public static void main(String[] args) {
        int[] nums1 = {1, 7, 11};
        int[] nums2 = {2, 4, 6};
        System.out.println(kSmallestPairs(nums1, nums2, 3));
    }

    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new ArrayList<>();
        //建立最小堆
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return (nums1[o1[0]]+nums2[o1[1]])-(nums1[o2[0]]+nums2[o2[1]]);
            }
        });

        int n1 = nums1.length;
        int n2 = nums2.length;

        //将nums1的所有索引全部入队。
        for (int i = 0; i < Math.min(n1,k); i++) {
            priorityQueue.offer(new int[]{i,0});
        }

        while (k-->0&&!priorityQueue.isEmpty()){
            int[] poll = priorityQueue.poll();
            res.add(Arrays.asList(nums1[poll[0]],nums2[poll[1]]));

            //最重要的是这里，更新nums2的索引与当前索引的组合。将其加入最小堆。
            if (++poll[1]<n2){
                priorityQueue.offer(poll);
            }
        }
        return res;
    }
}
